Орграф бинарного отношения

Определение

Для бинарного отношения \( $R \subseteq A \times A$ \) на конечном множестве \( A \) его **орграф** (ориентированный граф) \( $G_R = (V, E)$ \) определяется как:
- \( V = A \) (вершины — элементы множества)
- \( E = R \) (дуги — пары из отношения)

Связь свойств отношения со свойствами орграфа

1. **Рефлексивность**

• **Отношение**: \( $\forall a \in A: (a, a) \in R$ \)
• **Орграф**: У каждой вершины есть **петля** (дуга из вершины в себя)
• **Матрица смежности**: Все элементы на главной диагонали равны 1

2. **Антирефлексивность (иррефлексивность)**

• **Отношение**: $\forall a \in A: (a, a) \notin R$
• **Орграф**: Ни у одной вершины нет петель
• **Матрица смежности**: Все элементы на главной диагонали равны 0

3. **Симметричность**

• **Отношение**: \($\forall a, b \in A: (a, b) \in R \Rightarrow (b, a) \in R$\)
• **Орграф**: Если есть дуга \( a \to b \), то обязательно есть дуга \( b \to a \)
• **Матрица смежности**: Матрица симметрична относительно главной диагонали \( M = M^T \)

4. **Антисимметричность**

• **Отношение**: \( $\forall a, b \in A: (a, b) \in R \land (b, a) \in R \Rightarrow a = b$ \)
• **Орграф**: Между различными вершинами может быть не более одной дуги (либо только в одном направлении, либо вообще нет)
• **Матрица смежности**: Для \( i \neq j \), если \( M[i,j] = 1 \), то \( M[j,i] = 0 \)

5. **Асимметричность**

• **Отношение**: \( $\forall a, b \in A: (a, b) \in R \Rightarrow (b, a) \notin R$ \)
• **Орграф**: Нет симметричных пар дуг и нет петель
• **Матрица смежности**: Матрица антисимметрична и на диагонали все 0

6. **Транзитивность**

• **Отношение**: \( $\forall a, b, c \in A: (a, b) \in R \land (b, c) \in R \Rightarrow (a, c) \in R$ \)
• **Орграф**: Если существует путь длины 2 от \( a \) к \( c \) (через \( b \)), то существует и дуга \( $a \to c$ \)
• **Матрица смежности**: \( $M^2 \leq M$\) (в смысле покомпонентного сравнения), где \( $M^2$ \) — булево квадрат матрицы

7. **Полнота (связность)**

• **Отношение**: \( $\forall a, b \in A, a \neq b: (a, b) \in R \lor (b, a) \in R$ \)
• **Орграф**: Между любыми двумя различными вершинами есть хотя бы одна дуга
• **Матрица смежности**: Для всех $( i \neq j ): ( M[i,j] = 1$) или \( $M[j,i] = 1$)

8. **Эквивалентность**

• **Отношение**: Рефлексивно, симметрично и транзитивно
• **Орграф**: Граф состоит из полных симметричных подграфов (клик) с петлями у всех вершин
• **Матрица смежности**: Симметричная, с единицами на диагонали, блочно-диагональная

9. **Частичный порядок**

• **Отношение**: Рефлексивно, антисимметрично и транзитивно
• **Орграф**: Ациклический граф (кроме петель) с транзитивными замыканиями
• **Матрица смежности**: Треугольная (после топологической сортировки вершин)

1

1. **Строгий частичный порядок**
2. **Отношение**: Антирефлексивно, антисимметрично и транзитивно
3. **Орграф**: Ациклический ориентированный граф без петель
4. **Матрица смежности**: Строго треугольная (нули на диагонали)

Примеры

Пример 1: Отношение делимости на {1, 2, 3, 4, 6}

• R = {(1,1), (2,2), (3,3), (4,4), (6,6), (1,2), (1,3), (1,4), (1,6), (2,4), (2,6), (3,6)}
• Свойства: рефлексивно, антисимметрично, транзитивно → частичный порядок
• Орграф: есть петли, нет симметричных пар, есть транзитивные дуги

Пример 2: Отношение равенства

• R = {(a,a) | a ∈ A}
• Свойства: рефлексивно, симметрично, транзитивно → эквивалентность
• Орграф: только петли у всех вершин

Пример 3: Отношение "меньше" на натуральных числах

• R = {(a,b) | a < b}
• Свойства: антирефлексивно, асимметрично, транзитивно → строгий частичный порядок
• Орграф: нет петель, нет симметричных пар, есть транзитивные замыкания

Алгоритмические следствия

1. Проверка рефлексивности: проверить наличие всех петель — O(|V|)

2. Проверка симметричности: проверить все пары дуг — O(|E|)

3. Проверка транзитивности: проверить все тройки или использовать умножение матриц — O(|V|³)

4. Нахождение классов эквивалентности: поиск компонент сильной связности — O(|V|+|E|)

5. Проверка ацикличности: топологическая сортировка — O(|V|+|E|)

Таким образом, орграф является наглядным и полезным инструментом для анализа свойств бинарных отношений.